


#include <iostream>
#include <unordered_map>
using namespace std;

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};

using Node = TreeNode;

class Solution
{ 
public:
    bool checkSubTree(TreeNode* t1, TreeNode* t2)
    {
        if (nullptr == t1 && nullptr == t2)
            return true;

        if ((nullptr == t1 && t2) ||
            (nullptr == t2 && t1))
            return false;

        if (t1->val == t2->val && _check(t1, t2))
            return true;

        return checkSubTree(t1->left, t2) || checkSubTree(t1->right, t2);
    }

    int pathSum1(TreeNode* root, int sum)
    {
        if (nullptr == root)
            return 0;

        int ans = _pathSum1(root, sum);

        ans += pathSum1(root->left, sum);
        ans += pathSum1(root->right, sum);

        return ans;
    }

    unordered_map<long long, int> prefix;
    int pathSum2(TreeNode* root, int sum) 
    {
        //prefix[0] = 1;
        prefix[0]++;

        return dfs(root, 0, sum);
    }

private:
    int _pathSum1(Node* root, int sum)
    {
        if (nullptr == root)
            return 0;

        int ans = 0;

        if (root->val == sum)
            ++ans;

        int lf = _pathSum1(root->left, sum - root->val);
        int rg = _pathSum1(root->right, sum - root->val);

        return lf + rg + ans;
    }

    bool _check(Node* t1, Node* t2)
    {
        if (nullptr == t1 && nullptr == t2)
            return true;

        if ((nullptr == t1 && t2) ||
            (nullptr == t2 && t1))
            return false;

        if (t1->val != t2->val)
            return false;

        return _check(t1->left, t2->left) && _check(t1->right, t2->right);
    }

    int dfs(TreeNode* root, long long curr, int sum) 
    {
        if (!root) 
        {
            return 0;
        }

        int ret = 0;
        curr += root->val;
        if (prefix.count(curr - sum)) 
        {
            ret = prefix[curr - sum];
        }

        prefix[curr]++;
        ret += dfs(root->left, curr, sum);
        ret += dfs(root->right, curr, sum);
        prefix[curr]--;

        return ret;
    }

};

Node* GetTree()
{
    Node* node5 = new Node(5);
    Node* node4 = new Node(4);
    Node* node8 = new Node(8);
    Node* node11 = new Node(11);
    Node* node13 = new Node(13);
    Node* node44 = new Node(4);
    Node* node7 = new Node(7);
    Node* node2 = new Node(2);
    Node* node55 = new Node(5);
    Node* node1 = new Node(1);

    node5->left = node4, node5->right = node8;
    node4->left = node11;
    node8->left = node13, node8->right = node44;
    node11->left = node7, node11->right = node2;
    node44->left = node55, node44->right = node1;

    return node5;
}

void Test1()
{
    int sum = 22;
    Solution().pathSum2(GetTree(), sum);
}

//int main()
//{
//    Test1();
//
//
//	return 0;
//}

#include <iostream>
#include <vector>
#include <cmath>
#include <set>
using namespace std;

bool isPrime(int x)
{
    for (int i = 2; i < sqrt(x) + 1; ++i)
    {
        if (0 == x % i)
            return false;
    }

    return true;
}

void fact(int n, vector<int>& primes)
{
    for (int i = 2; i <= sqrt(n) + 1; ++i)
    {
        if (0 == n % i)
        {
            primes.push_back(i);
            fact(n / i, primes);
            return;
        }
    }
    primes.push_back(n);
}

int main()
{
    int n = 0;

    cin >> n;
    if (isPrime(n))
    {
        cout << -1 << endl;
        return 0;
    }

    vector<int> primes;
    fact(n, primes);

    set<int> s(primes.begin(), primes.end());
    int mini = 1000001;

    for (const auto& prime : s)
    {
        for (int i = n-prime+1; i <= n; ++i)
        {
            if (isPrime(i))
                continue;

            vector<int> v;
            fact(i, v);
            int maxg = 0;

            for (const auto& factor : v)
            {
                maxg = max(maxg, factor);
            }
            mini = min(i - maxg + 1, mini);
        }
    }

    cout << (mini == 1000001 ? -1 : mini) << endl;

    return 0;
}